package com.example.sorts11.sort;

import javafx.scene.effect.BlendBuilder;

/**
 * 向下冒泡算法
 * 希尔排序
 * @auther lijiewei
 * @date 2021/8/25 16:22
 */
public class SortsAddOn {

    /**
     * 向下冒泡：将下标i(从0开始)，和后面每个元素比较，下标数值更大时进行交换，交换后用下标i对应的新值和后续元素比较
     * @param arr 数组
     * @return
     * @author lijiewei
     * @date   2021/8/25 16:25
     */
    public static void bubbleDownSort(int[] arr) {
        int len = arr.length;
        if (len == 1) {
            return;
        }
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                if (arr[i] > arr[j]) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

    /**
     * 希尔排序：1. 设置步长step, 划分 i*step+i 的数据为一组数据进行插入排序
     * 2. 缩短步长step, 重新分组后进行插入排序，直至 step 为1
     * @param arr 数组
     * @return
     * @author lijiewei
     * @date   2021/8/25 16:40
     */
    public static void shellSort(int[] arr) {
        int len = arr.length;
        if (len == 1) {
            return;
        }

        //设置步长
        int step = len / 2;
        //循环缩小步长
        while (step >= 1) {
            for (int i = step; i < len; i++) {
                int value = arr[i];
                //偏移量
                int j = i - step;
                for (; j >= 0; j-=step) {
                    if (value < arr[j]) {
                        arr[j+step] = arr[j];
                    } else {
                        break;
                    }
                }
                arr[j+step] = value;
            }
            step = step / 2;
        }
    }
}
